package com.xsherl.leetcode.solution;

import com.xsherl.leetcode.utils.PrintUtils;

import java.util.ArrayList;
import java.util.List;

public class TextJustification {

    /**
     * 依次统计字符长度（因为两个单词中间必然有空格，所以我们每次统计字符长度时需要加上空格长度。），如果字符长度超过最大长度，说明这个单词是放在下一行。
     * 这时我们可以轻易算出需要多少个空格填充剩下字符，平均到每个单词之间又是多少个空格。
     * 需要注意的是，最后一行的单词中间不需要填充多余的空格，这时我们将多余的空格填充到尾部。
     *
     */
    public List<String> fullJustify(String[] words, int maxWidth) {
        List<String> res = new ArrayList<>();
        int len = words.length;
        int charLen = 0, rowCount = 0;
        for (int i = 0; i < len; ++i){
            // 每次统计字符长度都加上一个空格字符长度
            charLen += words[i].length() + 1;
            if (charLen - 1 > maxWidth){
                StringBuilder sb = new StringBuilder();
                // 如果这一行只有一个字符，直接将空格加在字符后面
                if (rowCount == 1){
                    sb.append(words[i - 1]);
                    int w = maxWidth - words[i - 1].length();
                    while (w-- > 0){
                        sb.append(' ');
                    }
                } else {
                    // 移除当前字符串长度
                    charLen -= words[i].length() + 1;
                    // 移除空格字符长度
                    charLen -= rowCount;
                    // 计算每个字符间空格数量
                    int spaceWidth = (maxWidth - charLen) / (rowCount - 1);
                    // 计算不能均分的空格数量
                    int raminSpace = (maxWidth - charLen) % (rowCount - 1);
                    // 只需要为这一行的前 n - 1 个单词后面添加空格
                    for (int j = i - rowCount; j <= i - 2; ++j){
                        sb.append(words[j]);
                        int w  = spaceWidth;
                        // 由题意：如果某一行单词间的空格不能均匀分配，则左侧放置的空格数要多于右侧的空格数
                        // 因此不能均分的空格没有分配完全，这个单词后面需要多一个空格
                        if (raminSpace-- > 0 ){
                            w++;
                        }
                        while (w-- > 0){
                            sb.append(' ');
                        }
                    }
                    sb.append(words[i - 1]);
                }
                res.add(sb.toString());
                charLen = words[i].length() + 1;
                rowCount = 0;
            }
            rowCount++;
        }
        StringBuilder sb = new StringBuilder();
        for (int i = len - rowCount; i < len - 1; ++i){
            sb.append(words[i]).append(' ');
        }
        sb.append(words[len - 1]);
        while (charLen++ <= maxWidth){
            sb.append(' ');
        }
        res.add(sb.toString());
        return res;
    }

    public static void main(String[] args) {
//        String[] words = {"What","must","be","acknowledgment","shall","beeeeee"};
        String[] words = {"This", "is", "an", "example", "of", "text", "justification."};
        int maxWidth = 16;
        List<String> strings = new TextJustification().fullJustify(words, maxWidth);
        strings.forEach(s -> {
            System.out.println(s.replace(' ', '.') + "-------------" + s.length());
        });
    }
}
